// https://leetcode.cn/problems/reverse-linked-list/

// 题干：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

// 示例：输入：head = [1,2,3,4,5]
//       输出：[5,4,3,2,1]

// 碎语：函数的作用是什么？返回一个逆转后的链表的头结点，那么将从第二个节点到最后节点的链表倒转，再链接头结点
//       因此，返回一个节点指针

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution
{
public:
    ListNode* reverseList(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr){
            return head;
        }

        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return newHead;
    }
};

int main()
{
    Solution sol;

    auto l1 = new ListNode(1);
    l1->next = new ListNode(2);
    l1->next->next = new ListNode(3);
    l1->next->next->next = new ListNode(4);
    l1->next->next->next->next = new ListNode(5);

    ListNode* index = sol.reverseList(l1);
    while (index != nullptr){
        cout << index->val << " ";
        index = index->next;
    }
    cout << endl;

    return 0;
}